"""
题目：给定一个无权图和起点，使用 BFS 计算起点到所有可达顶点的最短距离（起点到自身距离为 0，不可达顶点距离为 - 1）。
"""


class Graph:
    def __init__(self, is_directed=False):
        self.vertices = {}
        self.is_directed = is_directed

    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = []

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.vertices[v1].append(v2)
        if not self.is_directed:
            self.vertices[v2].append(v1)

    def get_bfs_distances(self, start):
        """BFS计算起点到所有可达顶点的距离（无权图）"""
        if start not in self.vertices:
            return {}  # 起点不存在，返回空字典

        # 初始化距离字典：默认-1（不可达），起点距离0
        distances = {v: -1 for v in self.vertices}
        distances[start] = 0
        visited = set([start])
        queue = [start]  # BFS队列

        while queue:
            current = queue.pop(0)
            # 遍历当前顶点的邻接顶点
            for neighbor in self.vertices[current]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    distances[neighbor] = distances[current] + 1  # 距离+1
                    queue.append(neighbor)

        return distances


# 测试
if __name__ == "__main__":
    undir_graph = Graph()
    undir_graph.add_edge(0, 1)
    undir_graph.add_edge(0, 2)
    undir_graph.add_edge(1, 3)
    undir_graph.add_edge(2, 3)
    undir_graph.add_edge(3, 4)

    distances = undir_graph.get_bfs_distances(0)
    print("起点0到各顶点的距离:", distances)
    # 输出: {0:0, 1:1, 2:1, 3:2, 4:3}